class Solution {
    vector<vector<int>> result;
    vector<int> tmp;

    void backTracking(vector<int>& candidates, int target, int sum, int startIndex)
    {
        if (sum > target) return;
        if (sum == target)
        {
            result.push_back(tmp);
            return;
        }
        for (int i = startIndex; i < candidates.size(); ++i)
        {
            tmp.push_back(candidates[i]);
            sum += candidates[i];
            backTracking(candidates, target, sum, i);
            tmp.pop_back();
            sum -= candidates[i];
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backTracking(candidates, target, 0, 0);
        return result;
    }
};